package org.hot100_6.leetcode15;

import org.algorithm.Stack.ArrayStack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution2 {

    public static void main(String[] args) {
        int [] test = {-1,0,1,2,-1,-4};
        threeSum(test);
    }

    public static List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();

        int n = nums.length;

        Arrays.sort(nums);

        for (int i = 0; i < n; i++) {
            if (nums[i]>0){
                break;
            }

            if (i>0 && nums[i]==nums[i-1]){
                continue;
            }

            int left = i+1;
            int right = n-1;

            while (left<right){
                int sum = nums[i]+nums[left]+nums[right];
                List<Integer> item = new ArrayList<>();
                if (sum ==0){
                    item.add(nums[i]);
                    item.add(nums[left]);
                    item.add(nums[right]);
                    result.add(item);
                    while (left<right && nums[left]==nums[left+1]){
                        left++;
                    }
                    while (left<right  && nums[right]==nums[right-1]) {
                        right--;
                    }
                    left++;
                    right--;
                }else if (sum>0){
                    right--;
                }else {
                    left++;
                }
            }
        }

        return result;
    }
}
